package likou.tanxin;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/15 10:14
 */
public class _948 {
    public static void main(String[] args) {
        System.out.println(bagOfTokensScore(new int[]{33, 4, 28, 24, 96}, 35));
    }

    //最优解，每次保存当前最优解！！
    public static int bagOfTokensScore(int[] tokens, int P) {
        if (tokens.length == 0) {
            return 0;
        }
        //尽可能多的得到能量并保证还有可以获得分数的令牌
        Arrays.sort(tokens);
        int daan = 0;
        int left = 0;
        int right = tokens.length - 1;
        while (left <= right) {
            int nowL = tokens[left];
            int nowR = tokens[right];
            if (P < tokens[left]) {
                if (daan == 0) {
                    return 0;
                }
                if (right - left < 2) {
                    return daan;
                } else {
                    //只有多一个，才是赚的！！！
                    int nextR = right;
                    int nextL = left + 1;
                    int nowP = P + nowR;
                    int nowH = nowL + tokens[nextL];
                    while (nextR > nextL) {
                        if (nowP >= nowH) {
                            break;
                        }
                        nextR--;
                        nextL++;
                        nowP += tokens[nextR];
                        nowH += tokens[nextL];
                    }
                    if (nextR < nextL || nowH > nowP) {
                        return daan;
                    } else {
                        P = nowP - nowH;
                        right = nextR - 1;
                        left = nextL + 1;
                        daan++;
                        if (right == left) {
                            return daan;
                        }
                    }
                }
            } else {
                daan++;
                P -= nowL;
                left++;
            }
        }
        return daan;
    }


    //    最优解，要么继续，要么停，所以直接记录当前最大的就行了
    public int bagOfTokensScore2(int[] tokens, int P) {
        Arrays.sort(tokens);
        int i = 0;
        int j = tokens.length - 1;

        int res = 0;
        int result = 0;
        while (i <= j) {
            if (P >= tokens[i]) {
                P = P - tokens[i];
                res++;
                i++;
            } else {
                if (res == 0) {
                    break;
                }
                P += tokens[j];
                j--;
                res--;
            }
            result = Math.max(result, res);
        }
        return result;
    }
}
